package swordoffer.offer10_1;

public class MemoRecursion {
    /**
     * 记忆化递归
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        int[] memo = new int[n + 1];
        return climbStairs(n, memo);
    }

    public int climbStairs(int n, int[] memo) {
        if (memo[n] > 0) {
            return memo[n];
        }
        if (n < 3) {
            return n;
        }
        int first = climbStairs(n - 1, memo);
        memo[n - 1] = first;
        int second = climbStairs(n - 2, memo);
        memo[n - 2] = second;
        int res = first + second;
        memo[n] = res;
        return res;
    }
}
